package com.shuang.dp34;

class Solution {
    //根据题意可知 就是求两个数组的最长公共子序列的长度
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
         //dp[i][j]：长度为[0, i - 1]的nums1与长度为[0, j - 1]的nums2的最长公共子序列长度为dp[i][j] 为了初始化方便
        int[][] dp = new int[nums1.length + 1][nums2.length + 1]; 

        //递推：
        //两个数组 i-1 和 j-1 位置的元素相等 则dp[i][j] = dp[i - 1][j - 1] + 1;
        //i-1和j-1 位置元素不相等 dp[i][j] 由两种情况得来 第一种是去掉第一个数组的位置i-1的元素即dp[i-1][j]第二种去掉第二个数组j-1位置的元素 取两种情况的最大值

        //初始化第一行和第一列直接都是0即可

        //遍历
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[nums1.length][nums2.length];
    }
}